#include <stdio.h>
#include <stdlib.h>
int partition(int arr[], int low, int high) {
  int key;
  key = arr[low];
  while (low < high) {
    while (low < high && arr[high] >= key)
      high--;
    if (low < high)
      arr[low++] = arr[high];
    while (low < high && arr[low] <= key)
      low++;
    if (low < high)
      arr[high--] = arr[low];
  }
  arr[low] = key;
  return low;
}
void quick_sort(int arr[], int start, int end) {
  if (start < end) {
    int pos = partition(arr, start, end);
    quick_sort(arr, start, pos - 1);
    quick_sort(arr, pos + 1, end);
  }
}

int main(void) {
  int n=10000000;
  int *a=(int*)malloc(sizeof(int)*n);
  int i;
  for(i=0;i<n;i++)a[i]=rand();
  long long start=clock();
  quick_sort(a, 0, n - 1);
  long long end=clock();
  printf("%.2f\n",(end-start)/1000.0);
  free(a);
  return 0;
}
